'''
Created on Jun 4, 2010

@author: roni
'''
from gde import GDE
from cvxopt import matrix
from cvxopt import solvers
import time
import logging


class LinearProgrammingGde(GDE):
    '''
    classdocs
    '''
    
    ACCURACY_BUFFER = 0.0005

    def __init__(self):
        '''
        Constructor
        '''
        GDE.__init__(self)
        self.single_diagnosis = True
        self.name = "LP"

    def diagnose(self,conflict_agents, candidates, abnormal_nodes = set()):
        ''' Overrides GDE method. Returns a set of diagnosises 
        param conflict_agents - agents that still have an unexplained conflict 
        param possible_abnormal_nodes - nodes that may be abnormal, which may explain conflict of agents
        param abnormal_nodes - nodes that are assumed to be abnormals (satisfied previous agents)'''
       
        diagnosis = self.solve(conflict_agents, candidates)
        self.diagnosises.append(diagnosis)       
        if self.single_diagnosis==True:
            return

        # Multiple diagnoses
        tested_candidates = [candidates]
        closed_list = []
        open_list =[]
        open_list.append(diagnosis)
        while len(open_list)>0:
            root_diagnosis = open_list.pop()
            closed_list.append(root_diagnosis)   
            candidates = set(root_diagnosis.keys())                                             
            for node in root_diagnosis.keys():
                new_candidates =  candidates.difference([node])
                if new_candidates not in tested_candidates:
                    tested_candidates.append(new_candidates)
                    diagnosis = self.solve(conflict_agents, new_candidates)
                    if diagnosis is not None and diagnosis not in self.diagnosises:
                        self.diagnosises.append(diagnosis)
                        open_list.append(diagnosis)
        
    def solve(self,conflict_agents, candidates):
        ''' Runs LP on equations, returns a diagnosis (abnormal node to delay) '''
        # Create an index to every candidate       
        self.candidate_to_index = dict()
        index = 0
        for candidate in candidates:
            self.candidate_to_index[candidate]=index
            index=index+1

        # Add target function
        target_function = self.create_target_function(len(candidates))
        # Add constraints
        (equations, results_vector) = self.create_constraints_equations(conflict_agents, candidates)

        target_function = matrix(target_function) 
        variables_matrix = matrix(equations)
        variables_matrix = variables_matrix.trans()
        results_matrix = matrix(results_vector)
        
        solvers.options['show_progress']=False # Removes printouts of solver
        solution=solvers.lp(target_function,variables_matrix,results_matrix)
        
        # If maximum iterations have been reached, increase the max iterations until solution has been found
        if solution['status'] == 'unknown':
            logging.info("Probably max iterations reached")
            original_max_iter = -1
            if solvers.options.has_key('maxiters'):
                original_max_iter = solvers.options['maxiters']
            else:
                solvers.options['maxiters']=200
            while solution['status'] == 'unknown':
                solution=solvers.lp(target_function,variables_matrix,results_matrix)
                solvers.options['maxiters']=solvers.options['maxiters']*2
            if original_max_iter>0:
                solvers.options['maxiters'] = original_max_iter
            else:
                solvers.options.pop('maxiters')
        if solution['status']=='optimal':
            node_to_delay = dict()
            solution = solution['x']
            for candidate in candidates:
                delay = solution[self.candidate_to_index[candidate]]
                if abs(delay-0)>LinearProgrammingGde.ACCURACY_BUFFER:
                    node_to_delay[candidate] = delay
            return node_to_delay
        else:
            return None           

    
    
    def create_target_function(self,num_of_candidates):
        return [1.0 for i in xrange(num_of_candidates)]

    def create_constraints_equations(self,conflict_agents, candidates):
        equations = []        
        results_vector = [] 
        num_of_candidates = len(candidates)  
        for agent in conflict_agents:
            equation0 = [0.0 for i in xrange(num_of_candidates)]
            equation1 = [0.0 for i in xrange(num_of_candidates)]
            observed_delay=self.observed[agent]
            expected_delay=self.scenario.expected_delay[agent]
            for node in self.scenario.agent_to_path[agent][1:-1]:
                if node in candidates:
                    index = self.candidate_to_index[node]              
                    equation0[index]=2.0
                    equation1[index]=-2.0
            unexplained=observed_delay-expected_delay
            # Divide by link steps to escape accuracy errors and insignficant queuing delays.
            #unexplained= round(unexplained/Ns2Scenario.LINK_DELAY)*Ns2Scenario.LINK_DELAY
            equations.append(equation0)
            results_vector.append(unexplained+LinearProgrammingGde.ACCURACY_BUFFER)
            equations.append(equation1)
            results_vector.append(-unexplained+LinearProgrammingGde.ACCURACY_BUFFER)
        
        # Remove redundant rows
        unique_equations = []
        unique_results = []
        for i in xrange(len(equations)):
            if equations[i] not in unique_equations:
                unique_equations.append(equations[i])
                unique_results.append(results_vector[i])
        equations=unique_equations
        results_vector = unique_results
        
        # Add constraint to enforce no negative and no "over one" constraint unexpected delays
        for i in xrange(num_of_candidates):
            equation = [0.0 for j in xrange(num_of_candidates)]
            equation[i]=-1.0
            equations.append(equation)
            results_vector.append(0)
            equation = [0.0 for j in xrange(num_of_candidates)]
            equation[i]=1.0
            equations.append(equation)                        
            results_vector.append(1)        
        
        return (equations, results_vector)
